package org.xiaoxin.leetcode.array;

import java.util.*;

/**
 * 15. 三数之和
 * <p>
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[1] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * <p>
 * 示例 2：
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * <p>
 * 示例 3：
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 * <p>
 * 提示：
 * 3 <= nums.length <= 3000
 * -10^5 <= nums[i] <= 10^5
 * <p>
 * 难度：中等
 * 标签：数组、双指针、排序
 *
 * @author xiaoxin
 */
public class _15_threeSum {

    /**
     * 方法一：排序 + 双指针法（推荐）
     * 思路：先排序，然后固定一个数，用双指针在剩余数组中寻找两数之和
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1) 不考虑返回值的空间
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 提示：
        // 1. 首先对数组进行排序
        // 2. 遍历数组，固定第一个数 nums[i]
        // 3. 在 i+1 到 n-1 的范围内使用双指针寻找两数之和为 -nums[i]
        // 4. 注意去重：跳过重复的 nums[i]，以及重复的左右指针值
        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return result;
        }
        // 排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复的固定值
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

            while (left < right) {

                int sum = nums[left] + nums[right];


                if (sum == target) {

                    //找到了一个结果
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //排除 left 重复
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    //排除 right 重复
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;

                } else if (sum < target) {
                    //小了，左指针右移
                    left++;

                } else {
                    //大了，右指针左移
                    right--;
                }


            }


        }


        return result;
    }

    /**
     * 方法二：暴力法（不推荐，仅供理解）
     * 思路：三层循环遍历所有可能的三元组
     * 时间复杂度：O(n^3)
     * 空间复杂度：O(1) 不考虑返回值的空间
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        // 提示：
        // 1. 使用三层循环：i < j < k
        // 2. 检查 nums[i] + nums[j] + nums[k] == 0
        // 3. 使用 Set 去重复三元组
        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return result;
        }

        Set<String> hashSet = new HashSet<>();


        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        // 排序，保证顺序一致
                        list.sort(Comparator.naturalOrder());
                        // 去重
                        String key = list.get(0) + "_" + list.get(1) + "_" + list.get(2);
                        if (!hashSet.contains(key)) {
                            hashSet.add(key);
                            result.add(list);
                        }

                    }

                }
            }
        }


        return result;
    }

    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 15. 三数之和 - 测试用例 ===\n");

        // 示例 1
        int[] nums1 = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> expected1 = Arrays.asList(
                Arrays.asList(-1, -1, 2),
                Arrays.asList(-1, 0, 1)
        );
        testCase("示例 1", nums1, expected1);

        // 示例 2
        int[] nums2 = {0, 1, 1};
        List<List<Integer>> expected2 = new ArrayList<>();
        testCase("示例 2", nums2, expected2);

        // 示例 3
        int[] nums3 = {0, 0, 0};
        List<List<Integer>> expected3 = Arrays.asList(
                Arrays.asList(0, 0, 0)
        );
        testCase("示例 3", nums3, expected3);

        // 额外测试用例

        // 测试用例 4：没有解
        int[] nums4 = {1, 2, 3};
        List<List<Integer>> expected4 = new ArrayList<>();
        testCase("测试用例 4（没有解）", nums4, expected4);

        // 测试用例 5：多个解
        int[] nums5 = {-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
        // 预期结果需要根据实际算法确定
        testCase("测试用例 5（多个解）", nums5, null);

        // 测试用例 6：全负数
        int[] nums6 = {-4, -2, -1};
        List<List<Integer>> expected6 = new ArrayList<>();
        testCase("测试用例 6（全负数）", nums6, expected6);

        // 测试用例 7：全正数
        int[] nums7 = {1, 2, 3};
        List<List<Integer>> expected7 = new ArrayList<>();
        testCase("测试用例 7（全正数）", nums7, expected7);

        // 测试用例 8：包含重复元素
        int[] nums8 = {0, 0, 0, 0};
        List<List<Integer>> expected8 = Arrays.asList(
                Arrays.asList(0, 0, 0)
        );
        testCase("测试用例 8（包含重复元素）", nums8, expected8);
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, int[] nums, List<List<Integer>> expected) {
        System.out.println(testName + ":");
        System.out.println("输入数组: " + Arrays.toString(nums));
        if (expected != null) {
            System.out.println("期望结果: " + expected);
        } else {
            System.out.println("期望结果: 待确定");
        }

        _15_threeSum solution = new _15_threeSum();

        // 测试方法一
        int[] nums1 = nums.clone();
        List<List<Integer>> result1 = solution.threeSum(nums1);
        boolean method1Correct = expected == null || isResultEqual(result1, expected);
        System.out.println("方法一结果: " + result1 + " " +
                (expected == null ? "⏸️" : (method1Correct ? "✅" : "❌")));

        // 测试方法二
        int[] nums2 = nums.clone();
        List<List<Integer>> result2 = solution.threeSum2(nums2);
        boolean method2Correct = expected == null || isResultEqual(result2, expected);
        System.out.println("方法二结果: " + result2 + " " +
                (expected == null ? "⏸️" : (method2Correct ? "✅" : "❌")));

        if (expected != null) {
            boolean allCorrect = method1Correct && method2Correct;
            System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        } else {
            System.out.println("整体测试: ⏸️ 待实现");
        }
        System.out.println();
    }

    /**
     * 比较两个三元组列表是否相等（忽略顺序）
     */
    private static boolean isResultEqual(List<List<Integer>> result1, List<List<Integer>> result2) {
        if (result1.size() != result2.size()) {
            return false;
        }

        // 将每个三元组排序后比较
        List<String> set1 = new ArrayList<>();
        List<String> set2 = new ArrayList<>();

        for (List<Integer> triplet : result1) {
            List<Integer> sorted = new ArrayList<>(triplet);
            sorted.sort(Integer::compareTo);
            set1.add(sorted.toString());
        }

        for (List<Integer> triplet : result2) {
            List<Integer> sorted = new ArrayList<>(triplet);
            sorted.sort(Integer::compareTo);
            set2.add(sorted.toString());
        }

        set1.sort(String::compareTo);
        set2.sort(String::compareTo);

        return set1.equals(set2);
    }
} 